package datastructure.stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author XY
 * @version 1.0
 * @date 2022/2/24 9:16
 * @Description
 */
public class Leet234 {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //我们也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，
    // 快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

    public static boolean isPalindrome(ListNode head) {
        ListNode temp = head;
        if(temp== null){
            return false;
        }
        Deque<Integer> stack = new LinkedList();
        while(temp!=null){
            stack.push(temp.val);
            temp = temp.next;
        }
        temp = head;
        while(!stack.isEmpty()){
            if(temp.val != stack.pop()){
                return false;
            }
            temp = temp.next;
        }
        return true;

    }

    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        root.next = new ListNode(2);
        root.next.next = new ListNode(2);
        root.next.next.next = new ListNode(1);
        System.out.println(isPalindrome(root));
    }
}
